package demo6;

/**
 * @author xianyu
 * @version 1.0
 * @date 2020/7/20 19:16
 */
public class Main1 {

    public static void main(String[] args) {
        Node head = new Node(4);
        head.next = new Node(6);
        head.next.next = new Node(2);
        head.next.next.next = new Node(8);
        head.next.next.next.next  = new Node(6);
        head.show();
        findMidNode(head).show();
        head.show();
    }

    public static Node mergeSort(Node head){
        if(head==null||head.next==null) return head;
        Node middleHead = findMidNode(head);
        return merge(mergeSort(head),mergeSort(middleHead));
    }

    // 合并两个有序链表
    public static Node merge(Node p1,Node p2){
        Node dummy = new Node(-1);

        return null;
    }


    public static Node findMidNode(Node head){
        Node fast = head;
        Node slow = head;
        while(fast.next!=null&&fast.next.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Node newNode = slow.next;
        slow.next = null;
        return newNode;
    }
}




class Node{
    int val;
    Node next;

    Node(int val){
        this.val = val;
    }

    void show(){
        Node root = this;
        while(root!=null){
            System.out.print(root.val + " ");
            root = root.next;
        }
        System.out.println();
    }
}
